use std::ptr;
use std::fmt;

struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

#[derive(Debug)]
struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

impl<T> LinkedList<T>
where
    T: fmt::Display + fmt::Debug,
{
    pub fn new() -> LinkedList<T> {
	LinkedList {
	    head: None,
	}
    }

    pub fn from_iter<Iter>(iter: Iter) -> LinkedList<T>
    where
	Iter: Iterator<Item = T>,
    {
	let mut lst = LinkedList::new();
	let mut p: *mut Node<T> = ptr::null_mut();
	let mut pre;
	for item in iter {
	    let mut node = Box::new(Node::new(item));
	    let p2 = &mut (*node) as *mut Node<T>;
	    if p.is_null() {
		lst.head = Some(node);
	    } else {
		unsafe {
		    pre = &mut *p;
		}
		pre.next = Some(node);
	    }
	    p = p2;
	}
	lst
    }
}

impl<T> fmt::Display for LinkedList<T>
where
    T: fmt::Display + fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
	write!(f, "(")?;
	let mut first_time = true;
	let mut head = &self.head;
	while let Some(p) = head {
	    if first_time {
		first_time = false
	    } else {
		write!(f, " -> ")?;
	    }
	    write!(f, "{}", (*p).value)?;
	    head = &(*p).next;
	}
	write!(f, ")")
    }
}


impl<T> Node<T> {
    pub fn new(item: T) -> Node<T> {
	Node {
	    value: item,
	    next: None,
	}
    }
}

#[test]
fn test() {
    let ll = LinkedList::from_iter(vec![9, 2, 3, 4, 5, 6].into_iter());
    println!("{}", ll);
}
